{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "# 最短路"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### spfa"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "vscode": {
                    "languageId": "cpp"
                }
            },
            "outputs": [],
            "source": [
                "void spfa(){\n",
                "    queue<int> que;\n",
                "    que.push(s);\n",
                "    vis[s] = 1;\n",
                "    for (int i = 1; i <= n; i++)\n",
                "        dis[i] = INT_MAX;\n",
                "    dis[s] = 0;\n",
                "    while (que.size())\n",
                "    {\n",
                "        int t = que.front();\n",
                "        vis[t] = 0;\n",
                "        que.pop();\n",
                "        for (P *p = e[t]; p; p = p->next)\n",
                "            if (dis[p->to] > dis[t] + p->weight)\n",
                "            {\n",
                "                dis[p->to] = dis[t] + p->weight;\n",
                "                if (!vis[p->to])\n",
                "                    que.push(p->to), vis[p->to] = true;\n",
                "            }\n",
                "    }\n",
                "}"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### dijkstra"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "vscode": {
                    "languageId": "cpp"
                }
            },
            "outputs": [],
            "source": [
                "void dijkstra(){\n",
                "    priority_queue<pair<int, int>> pq;\n",
                "    pq.push(make_pair(0, s));\n",
                "    memset(dis, 0x3f, sizeof(dis));\n",
                "    dis[s] = 0;\n",
                "    while (pq.size())\n",
                "    {\n",
                "        pair<int, int> x = pq.top();\n",
                "        pq.pop();\n",
                "        if (vis[x.second])\n",
                "            continue;\n",
                "        vis[x.second] = true;\n",
                "        x.first = -x.first;\n",
                "        dis[x.second] = x.first;\n",
                "        for (P *p = e[x.second]; p; p = p->next)\n",
                "            if (dis[p->to] > x.first + p->weight)\n",
                "                pq.push(make_pair(-x.first - p->weight, p->to));\n",
                "    }\n",
                "}"
            ]
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": "Python 3 (ipykernel)",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.12.1"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}